\documentclass[11pt]{scrartcl}%article for more whitespace, scrartcl for less
\usepackage{cite}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{url}
\usepackage[utf8]{inputenc}
\usepackage{setspace}
\usepackage{hyperref}
\usepackage{algorithm}        % für Algorithmen
\usepackage{algorithmic}
\usepackage{multicol}
\usepackage[pdftex]{graphicx}
\usepackage{caption}      % für Algorithmen

\begin{document}
\title{
	\begin{small}181.190 Problem Solving and Search in Artificial Intelligence VU 2.0\end{small}\\
	Method Description for the Traveling Tournament Problem
}

\author{Fabian Fischer \thanks{e-mail: \texttt{fabianfshr@gmail.com}} \\
	Soheil Khosravipour \thanks{e-mail: \texttt{khosravipour@gmail.com}}
}
\maketitle

We decided to tackle the traveling tournament problem (TTP) as described in\cite{ENT} as the exercise of the course. We decided to try some local search techniques using different neighborhood structures. We base our method and ideas about the neighborhood structure on the paper by Di Gaspero and Schaerf\cite{GS06}. 

The problem broadly consists of two sub-problems: First, the schedule needs to be feasible, i.e. teams mustn't be too long at home nor too long away consecutively. Second, the total traveling distance should be minimized. This combination makes the TTP hard to solve with exact methods. 

\subsection*{Constraints}
The following hard constraints are imposed by TTP:
\begin{itemize}
	\item \emph{no repeat}: A match between two teams can never be followed in the next round by the other match between the same teams.
	\item \emph{at most away/home}: A team cannot play more than 3-4 consecutive games at home or away.
\end{itemize}

Each violated hard constraint is represented in the cost of the solution, with each violation increasing the cost $C$ by a value of $C*P, P > 0$. The parameter $P$ can be specified at startup of the program or it could be increased during runtime (i.e. allowing more constraint violations at the beginning of the program). 

\subsection*{Construction of Initial Solutions}
In our approach we start off with initial solutions that don't have to fulfill the hard constraints. For that we use the scheduling algorithm for the round-robin tournament\footnote{see \url{http://en.wikipedia.org/wiki/Round-robin\_tournament}}. In order to provide some randomization, the order of the teams is randomized. 

%With this approach and an input parameter $k$ we want to facilitate a multistart local search, with $k$ being the number of starting solutions - this would also make it possible to exploit multi-core computers easily. 

\subsection*{Neighborhood Structure}
In our approach we want to exploit several neighborhood structures. It must be tested how exactly these are chosen (when to switch between them), but in genereal these will be the basis for our local search. 

We will use tabu lists for the local searches and try to use delta functions as good as possible, thus reducing the time to recalculate the costs of the solutions.

\subsubsection*{SwapHomes}
This is a very simple neighborhood: For a given pair of teams $t_1, t_2$ we swap where they play, i.e. if orignally the game took place at $t_1$'s home, it then takes place at $t_2$'s home. This is taken from \cite{GS06}. We only choose $t_1 < t_2$. 

\subsubsection*{SwapTeams}
In this neighborhood the complete schedules of two teams $t_1, t_2$ are swapped. Also from \cite{GS06}. We only choose $t_1 < t_2$. 

\subsubsection*{SwapRounds}
Also from \cite{GS06} this neighborhood means that any two given rounds $r_1, r_2$ are being swapped for all teams. We only choose $r_1 < r_2$. 

\subsubsection*{Choosing a Neighborhood}
Our program stays within a neighborhood $N_i$ until $k$ iterations brought no improvements. Then another neighborhood $N_j, j \neq i$ is chosen and this way we try to improve within another neighborhood (similar to \cite{LRZ05}).

%Similar to the approach in \cite{LRZ05} variable neighborhood descent (VND) is used: We globally store the $m$ best solutions together with the last used neighborhood. %A solution is only saved if the last $k$ iterations in the latest neighborhood $N_i$ didn't bring any improvement. 

%We use one (or more) worker thread per neighborhood, each trying to improve within its neighborhood. If its current solution can't be improved further, it's being stored and the worker chooses another stored solution that was last improved by another neighborhood structure. 

\begin{small}
\bibliography{references}{}
\bibliographystyle{plain}
\end{small}
\end{document}
